import { _Array } from './Array'
import { Node } from './LinkedList'

export class ArrayQueue {
    constructor(capacity) {
        this.array = new _Array(capacity)
    }

    enqueue(e) { // O(1)
        this.array.addLast(e)
    }

    dequeue() { // O(n)
        return this.array.removeFirst()
    }

    getFront() { // O(1)
        return this.array.getFirst()
    }

    getSize() { // O(1)
        return this.array.getSize()
    }

    isEmpty() { // O(1)
        return this.array.isEmpty()
    }

    getCapacity() {
        return this.array.getCapacity()
    }
}

export class LoopQueue {
    constructor(capacity = 10) {
        this.data = new Array(capacity + 1)
        this.front = 0
        this.tail = 0
        this.size = 0
    }

    getCapacity() {
        return this.data.length - 1
    }

    isEmpty() { // O(1)
        return this.front === this.tail
    }

    getSize() { // O(1)
        return this.size
    }

    enqueue(e) { // O(1)
        if ((this.tail + 1) % this.data.length === this.front) {
            this.resize(this.getCapacity() * 2)
        }

        this.data[this.tail] = e
        this.tail = (this.tail + 1) % this.data.length
        this.size++
    }

    dequeue() { // O(1)
        if (this.isEmpty()) {
            throw new Error('Cannot dequeue from an empty queue.')
        }
        const frontEl = this.data[this.front]

        this.front = (this.front + 1) % this.data.length
        this.size--

        const newCapacity = Math.floor(this.getCapacity() / 2)
        if (this.size <= this.getCapacity() / 4 && newCapacity !== 0) {
            this.resize(newCapacity)
        }

        return frontEl
    }

    getFront() { // O(1)
        if (this.isEmpty()) {
            throw new Error('Queue is empty.')
        }

        return this.data[this.front]
    }

    resize(newCapacity) {
        const newData = new Array(newCapacity + 1)
        for (let i = 0; i < this.size; i++) {
            const index = (i + this.front) % this.data.length
            newData[i] = this.data[index]
        }

        this.data = newData
        this.front = 0
        this.tail = this.size
    }

    toString() {
        return '[' + this.data.filter(el => el).toString() + ']'
    }
}


export class LinkedListQueue {
    constructor() {
        this.head = null
        this.tail = null
        this.size = 0
    }

    getSize() {
        return this.size
    }

    isEmpty() {
        return this.size === 0
    }

    enqueue(e) {
        if (this.tail === null) {
            this.tail = new Node(e)
            this.head = this.tail

        } else {
            this.tail.next = new Node(e)
            this.tail = this.tail.next
        }

        this.size++
    }

    dequeue() {
        if (this.isEmpty()) {
            throw new Error('Cannot dequeue from an empty queue.')
        }

        const node = this.head
        this.head = this.head.next
        node.next = null

        if (this.head === null) {
            this.tail === null
        }
        this.size--

        return node.val
    }

    getFront() {
        if (this.isEmpty()) {
            throw new Error('Cannot dequeue from an empty queue.')
        }

        return this.head.val
    }

}